package com.julius.design.suanfa.tree;

import java.util.*;

/**
 * @author julius
 * @date 2021-11-09 上午 10:17
 * <p>
 *      给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
 *
 *      叶子节点 是指没有子节点的节点
 *
 *      链接：https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof
 * </p>
 */
public class PathSumTree {

    List<List<Integer>> ans = new LinkedList<>();
    Deque<Integer> path = new LinkedList<>();


    public List<List<Integer>> pathSum(TreeNode root,int target){
        dfs(root,target);
        return ans;
    }

    /**
     * DFS  +  回溯(递归形式)
     * @param root
     * @param target
     */
    public void dfs(TreeNode root,int target){
        if(root == null){
            return;
        }

        //添加路径
        path.offerLast(root.val);

        //计算目标值
        target = target - root.val;

        //判断是否满足路径条件 叶子节点达到目标和
        if(target == 0 && root.left == null && root.right == null){
            //将路径添加到结果中
            ans.add(new LinkedList<>(path));
        }

        //递归左子树
        dfs(root.left,target);
        //递归右子树
        dfs(root.right,target);
        //移除尾部节点  先进后出
        path.pollLast();

    }
}
